The present invention generally relates to an improved routing path finding method for use in the automatic routing/designing process of an LSI. More specifically, the present invention relates to a method for finding a routing path by applying a maze algorithm to a routing region partitioned into a plurality of grid points. In particular, the method of the present invention is adapted to find a routing path while satisfying a height or width constraint, imposed on a routing region, irrespective of the number of grid points included in the routing region.
A maze algorithm is one of known routing path finding techniques. The maze algorithm is disclosed, for example, by Frank Rubin in xe2x80x9cThe Lee Path Connection Algorithmxe2x80x9d, 1974 IEEE Transactions on Computers, Vol. c-23, No.9. Hereinafter, a known routing path finding method by the maze algorithm will be described with reference to FIG. 6.
First, in Step S10, interconnection information is input. Next, in Step S20, currently available grid points are extracted. Available grid points adjacent to a grid point in a list L, i.e., non-occupied grid points other than those specified as being located in a routing forbidden region and grid points in which terminals are located, are put into a list L1. At the same time, search directions from the grid point in the list L toward the respective available grid points are saved. And the grid points in the list L1 are extracted as available grid points.
Then, in Step S40, wire length costs are added while the available grid points, extracted in Step S20, are being searched. Every time one grid point is passed, a wire length cost of xe2x80x9c1xe2x80x9d is added. Next, a particular grid point, which can be reached from the source grid point at a minimum cost, is selected from the grid points in the list L1 and inserted into the list L.
Subsequently, in Step S50, it is determined whether or not a sink terminal has been reached. If the answer is YES, then the process advances to the next step S60. Otherwise, the process returns to Step S20. In other words, if the sink grid point is included in the list L, then the process advances to the next Step S60 of selecting a minimum cost path. Otherwise, the process returns to Step S20.
In Step S60, a minimum cost path is selected by tracing back the path in the search directions saved in Step S20.
Hereinafter, this process will be described in more detail with reference to FIG. 7. In the illustrated example, the number of interconnection layers is assumed to be one for the sake of simplicity. A routing region 20 is partitioned into a large number of grid points 30. In the routing region 20, terminals 10A, 10a, 10B, 10b, 10C and 10c and a routing forbidden region 21 are present.
In Step S10, interconnection information is input. The three enclosed numerals xe2x80x9c1xe2x80x9d, xe2x80x9c2xe2x80x9d and xe2x80x9c3xe2x80x9d attached to the terminals 10A, 10a, 10B, 10b, 10C and 10c indicate the numbers of respective nets and a pair of terminals with the same number (e.g., the terminals 10A and 10a with xe2x80x9c1xe2x80x9d) should be interconnected together.
For example, Net 1 can be routed in the following manner. The source terminal of Net 1 is the terminal 10A and the sink terminal thereof is the terminal 10a. In Step S20, first, the grid point where the source terminal 10A is placed is put into the list L. Then, available grid points adjacent to the source terminal 10A are put into the list L1. In this example, four grid points vertically and horizontally adjacent to the source terminal 10A are put into the list L1. At the same time, the search directions indicated by the arrows in FIG. 7 are saved. And the four grid points in the list L1 are extracted as available grid points.
Next, in Step S40, every time a single grid point has been passed, a wire length cost of xe2x80x9c1xe2x80x9d is added.
Then, at least one grid point with a minimum cost is/are selected from the list L1 and put into the list L. Since all of the four grid points currently present in the list L1 have the same cost of xe2x80x9c1xe2x80x9d, all of these four grid points are transferred into the list L.
Subsequently, since it is determined in Step S50 that the sink terminal 10a has not been reached yet, the process returns to Step S20. Thereafter, until the sink terminal 10a is reached, the same processing steps S20, S40 and S50 will be performed repeatedly.
In FIG. 7, the numbers in respective grid points represent the results obtained by adding the wire length costs together.
Suppose it is determined in Step S50 that the sink terminal grid 10a is included in the list L after the same set of process steps have been performed several times. Then a path, starting from the sink terminal 10a, is traced back in the search directions represented by the arrows in FIG. 7 in Step S60, thereby extracting a minimum cost path 40.
The routing results are illustrated in FIG. 8(a). FIG. 8(b) illustrates the results obtained by compacting downward the nets shown in FIG. 8(a). By performing compaction, not only nets but also terminals or routing forbidden region can be moved downward if there are any spaces available. Thus, the terminals 10A and 10c have been moved downward.
In a conventional routing path finding method, if routing is performed on a routing region partitioned into an insufficient number of grid points, then nets already routed sometimes prevent routing. Thus, to complete routing, a sufficient number of grid points should be prepared by adding grid points either from the beginning or after it has been determined that routing cannot be completed.
However, if height or width constraint is imposed on a routing region, the insertion of additional grid points possibly causes failure to comply with the constraint. A situation like this will be described with reference to FIGS. 9 through 11. The following example is a method for routing and designing a standard cell applicable to the design of an ASIC.
In FIGS. 9 through 11, a height constraint 101 is normally imposed on a standard cell 100. In the cell 100, transistors 50A and 50B, terminals 10 and power lines 60 are present. In the illustrated example, even though the cell actually has a multilevel interconnection structure, only the nets in the first layer (a first metallization layer 71 for a standard cell) are illustrated for the sake of simplicity.
In FIG. 9, a grid unit 32 is defined by uniformly partitioning the cell by the routing pitch of the first interconnection layer 71. If maze routing is completed on the grid with a uniform routing pitch, then the height constraint on the cell will be satisfied automatically. In other words, to complete routing successfully, a space should be provided beforehand for the nets passing between the transistors 50A and 50B.
However, it is very difficult to accurately estimate the space between the transistors before the routing is started. In fact, in an actual routing/designing process carried out manually, trials and errors are inevitable because routing and transistor spacing should be performed in parallel.
For example, if the space between the transistors 50A and 50B, obtained by pre-routing estimation, is too narrow as shown in FIG. 10, then routing should fail or cannot be completed because of the shortage in number of grid points. As can be seen, the terminals 10A and 10B cannot be interconnected together because there are no grid points available between them.
To solve this problem, according to a conventional method, a grid row with a height 32B narrower than the routing pitch (i.e., the normal grid unit 32A) is provided between the transistors 50A and 50B as shown in FIG. 11, thereby completing routing. Thereafter, spaces between transistors and between nets are adjusted through compaction to obtain the same results as those illustrated in FIG. 9.
However, if such a narrow grid row is inserted as shown in FIG. 11, then the number of grid points increases vertically. Thus, in accordance with this conventional method, the height constraint 101 on the cell 100 cannot be satisfied. In the foregoing example, a height constraint cannot be satisfied. A similar problem will happen when a width constraint is imposed.
Thus, to complete the routing process successfully even if the height or width constraint is imposed on the routing region, the present inventors proposed a routing path finding method in U.S. patent application Ser. No. 09/157,387. According to the proposed method, availability, or the number of grid points available for routing, is obtained for a grid column or row, on which the height or width constraint is imposed. And this availability is regarded as an additional cost required by the maze algorithm. Specifically, if a path to be found passes a grid column or row while the routing region is being searched, a passage cost is obtained based on the availability obtained for the grid column or row. And the passage cost is added to a routing path cost. In this manner, the routing path cost is always controlled so as to avoid failure to comply with the height or width constraint.
According to this routing path finding method, the routing process is much more likely to be completed successfully with the height and width constraints all satisfied, because the availability is defined for each grid column or row to meet the constraint. However, if a component to be placed (e.g., transistor) or a routing forbidden region overlaps a plurality of grid columns or rows in the routing region, then routing might be impossible, even if it has been determined by the availability that the routing is possible. This is because actually two routing paths might pass a single grid point in the grid column or row with that availability.
An object of the invention is providing a routing path finding method for an automatic routing/designing process of an LSI with the height or width constraint, imposed on a routing region, satisfied without adding any extra grid column or row in the direction in which the constraint is imposed.
To achieve this object, according to the present invention, multiple availabilities, not the single availability, are obtained for a single grid column or row in the routing region.
In addition, according to the present invention, a component (e.g., transistor) to be placed over multiple grid points is not fixed at a position. Instead, if there is any open net with that component fixed, then the component is moved to an appropriate position, thereby arranging a series of available grid points in the column or row direction. In this manner, the open net can be made routable through these available grid points.
An inventive method is adapted to find a routing path during an automated routing/designing process of an LSI by applying a maze algorithm to a routing region partitioned into multiple grid points arranged in columns and rows. In accordance with the maze algorithm, a path cost is calculated by adding a cost every time one of the grid points is passed. The method includes the step of a) extracting multiple sub-regions from each said column or row in the routing region. The sub-regions are formed by getting the column or row partitioned by a component like a transistor and a routing forbidden region existing in the routing region. The method further includes the steps of: b) obtaining a parameter for each said sub-region, which has been extracted in the step a), based on the number of nets that can pass the sub-region and the number of nets already routed in the sub-region; and c) calculating, using the parameter obtained in the step b), the cost to be added every time one of the grid points is passed.
Another inventive method is also adapted to find a routing path during an automated routing/designing process of an LSI by applying a maze algorithm to a routing region partitioned into multiple grid points arranged in columns and rows. In accordance with the maze algorithm, a routing path cost is calculated by adding a cost every time one of the grid points is passed responsive to a request that terminals of a component like a transistor, placed in the routing region, be interconnected. The method includes the steps of: a) moving the component such that available ones of the grid points are arranged in line if there is any open net between any pair of the terminals to be interconnected; and b) recalculating the routing path cost after the step a) has been performed.
Still another inventive method is also adapted to find a routing path during an automated routing/designing process of an LSI by applying a maze algorithm to a routing region partitioned into multiple grid points arranged in columns and rows. In accordance with the maze algorithm, a routing path cost is calculated by adding a cost every time one of the grid points is passed responsive to a request that terminals of a component like a transistor, placed in the routing region, be interconnected. The method includes the step of a) extracting multiple sub-regions from each said column or row in the routing region. The sub-regions are formed by getting the column or row partitioned by the component and a routing forbidden region. The method further includes the steps of: b) obtaining a parameter for each said sub-region, which has been extracted in the step a), based on the number of nets that can pass the sub-region and the number of nets already routed in the sub-region; c) calculating, using the parameter obtained in the step b), the cost to be added every time one of the grid points is passed; d) moving the component such that available ones of the sub-regions are arranged in line if there is any open net between any pair of the terminals to be interconnected; and e) recalculating the routing path cost by performing the steps b) and c) after the step d) has been performed.
In one embodiment of the present invention, the parameter obtained in the step b) for each said sub-region is preferably availability of grid points. The availability is obtained by subtracting the number of grid points occupied by the nets already routed from the number of grid points included in the sub-region.
In another embodiment of the present invention, the component may overlap at least two of the grid columns or at least two of the grid rows.
In still another embodiment, the method may further include the step of determining, after the component has been moved, whether or not there is any sub-region in which the number of nets already routed exceeds the number of nets that can pass the sub-region. If there is any such sub-region in which the number of nets already routed exceeds the number of nets that can pass the sub-region, then the method may further include the step of rerouting the nets passing the sub-region.
The present invention also provides a computer-readable storage medium having stored thereon a routing path finding program, which implements the inventive routing path finding method applicable to the automatic routing/designing process.
According to the present invention, multiple sub-regions are extracted from each of the grid columns or rows in which a component or routing forbidden region is located, and a parameter representing the availability of grid points is obtained for each of these sub-regions. Thus, compared to the method of obtaining a single availability for each grid column or row as proposed by us in the above-identified patent application, a far greater number of availability information items can be obtained from the routing region. Accordingly, even if a height or width constraint has been imposed on the routing region, all of the nets are much more likely to be routed successfully with that constraint fully satisfied.
In addition, according to the present invention, if the existence of a component, like a transistor, overlapping multiple grid points makes at least net open (or non-routable), then the component is moved to arrange available grid points in line along a column or row. Thus, the open net can be routed through these grid points.